#include "common.h"

int flg[9];
int flg1[20];
int flg2[20];
int m;
vector<vector<string>> ans;
void dfs(vector<string>& t, int h)
{
	if (h == m)
	{
		ans.push_back(t);
		return;
	}
	string tt;
	for (int i = 0; i < m; i++)
	{
		tt.push_back('.');
	}
	int j = 0;
	int p1, p2;
	for (int i = 0; i < m; i++)
	{
		if (flg[i]) continue;
		if (h >= i)
		{
			p1 = h - i;
		}
		else
		{
			p1 = i - h + m - 1;
		}
		int j = m - 1 - i;
		if (h >= j)
		{
			p2 = h - j;
		}
		else
		{
			p2 = j - h + m - 1;
		}
		if (flg1[p1] || flg2[p2]) continue;
		tt[i] = 'Q';
		flg[i] = flg1[p1] = flg2[p2] = 1;
		t.push_back(tt);
		dfs(t, h + 1);
		t.pop_back();
		tt[i] = '.';
		flg[i] = flg1[p1] = flg2[p2] = 0;
	}
}
vector<vector<string>> solveNQueens(int n)
{
	m = n;
	vector<string> t;

	dfs(t, 0);
	return ans;
}